/**
 * FileName:Exercise1403.c
 * ------------------------------------------------------------------------------------------------------------
 * 14.3 Develop a hash function for string keys based on the idea of loading 4 bytes at a time,
 * then performing arithmetic operations on 32 bits at a time.
 *
 * Compare the time required for this function with the times for Program 14.1 for 4-, 8-, 16-, and 32-byte keys.
 * ------------------------------------------------------------------------------------------------------------
 */

#include <stdio.h>    // For printf, perror
#include <stdlib.h>   // For malloc, free, rand, srand
#include <string.h>   // For strlen, memcpy
#include <time.h>     // For clock, time
#include <stdint.h>   // For uint32_t, uint8_t (important for 32-bit operations)

// 函数声明
int hash_1401(char *, int);
int hash_optimized_4byte(char *, int);

double measure_hash_time(int (*hash_func)(char*, int), char** keys, int num_keys, int M);
char* generate_random_string(size_t length);
void test_4byte_key();
void test_8byte_key();
void test_16byte_key();
void test_32byte_key();

// ============================== 优化函数实现 ==============================
int hash_1401(char *v, int M) {
    int h = 0;
    int a = 127;

    for (; *v != '\0'; ++v) {
        h = (a*h + *v) % M;
    }

    return h;
}

int hash_optimized_4byte(char *v, int M) {
    int h = 0;
    int a = 127;

    int len = strlen(v);
    int i;
    for (i = 0; i + 3 < len; i+=4) {
        uint32_t word;
        // 直接将4个字节解释为uint32_t
        // 注意：这里涉及字节序，如果考虑跨平台，可能需要手动组合字节
        // 但对于性能测试，这种直接内存解释通常是最快的。
        memcpy(&word, &v[i], sizeof(uint32_t));
        h = (a*h + word) % M;
    }

    for (; i < len; ++i) {
        h = (h * 127 + v[i]) % M; // 使用 Program 14.1 的基数处理剩余字符
    }

    return h;
}

// ============================== Helper Functions for Testing ==============================

// 生成指定长度的随机字符串 (包含可见ASCII字符，避免空字符)
char* generate_random_string(size_t length) {
    char* str = (char*)malloc(length + 1); // +1 for null terminator
    if (!str) return NULL;
    for (size_t i = 0; i < length; ++i) {
        // 生成可见ASCII字符，避免0作为'\0'提前终止字符串
        str[i] = 33 + (rand() % 94); // ASCII range 33 ('!') to 126 ('~')
    }
    str[length] = '\0'; // Null-terminate the string
    return str;
}

// 测量哈希函数执行时间
double measure_hash_time(int (*hash_func)(char*, int), char** keys, int num_keys, int M) {
    clock_t start, end;
    double cpu_time_used;
    volatile int dummy_hash_result; // Use volatile to prevent compiler optimizing out the hash call

    start = clock();
    for (int i = 0; i < num_keys; ++i) {
        dummy_hash_result = hash_func(keys[i], M); // Call the hash function
    }
    end = clock();
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    return cpu_time_used;
}

// ============================== Main Test Program ==============================
int main(int argc, char* argv[]) {
    test_4byte_key();
    test_8byte_key();
    test_16byte_key();
    test_32byte_key();
    return 0;
}

void test_4byte_key() {
    srand(time(NULL)); // Initialize random seed for reproducibility

    // Define hash table size M (a large prime number is usually good)
    const int M = 99991; // Common choice for hash table sizes

    // Define the key length for this specific test
    // Exercise 14.3 asks for comparison for 4-, 8-, 16-, and 32-byte keys.
    // For this specific request, we focus on 4-byte keys first.
    size_t test_key_length = 4; // Testing for 4-byte keys as per your request

    // Number of keys to hash for each length
    const int NUM_TEST_KEYS = 100000; // 10万个键

    printf("Comparing hash function performance for %zu-byte keys (M = %d):\n", test_key_length, M);
    printf("-------------------------------------------------------------------\n");

    // --- Generate random string keys for the current length ---
    char** test_keys = (char**)malloc(NUM_TEST_KEYS * sizeof(char*));
    if (!test_keys) {
        perror("Failed to allocate memory for test_keys array");
        return ;
    }
    for (int i = 0; i < NUM_TEST_KEYS; ++i) {
        test_keys[i] = generate_random_string(test_key_length);
        if (!test_keys[i]) {
            perror("Failed to generate random string key");
            // Clean up already allocated strings before exiting
            for (int j = 0; j < i; ++j) free(test_keys[j]);
            free(test_keys);
            return ;
        }
    }

    // --- Measure time for Program 14.1 hash function ---
    double time_hash_1401 = measure_hash_time(hash_1401, test_keys, NUM_TEST_KEYS, M);
    printf("Program 14.1 Hash (char by char): %f seconds\n", time_hash_1401);

    // --- Measure time for Optimized hash function ---
    double time_hash_optimized_4byte = measure_hash_time(hash_optimized_4byte, test_keys, NUM_TEST_KEYS, M);
    printf("Optimized Hash (4 bytes at a time): %f seconds\n", time_hash_optimized_4byte);

    // --- Calculate and print speedup ---
    if (time_hash_1401 > 0 && time_hash_optimized_4byte > 0) {
        printf("Speedup (14.1 / Optimized): %.2fx\n", time_hash_1401 / time_hash_optimized_4byte);
    } else {
        printf("Speedup (14.1 / Optimized): Cannot calculate (one of the times is zero or invalid)\n");
    }
    printf("\n");

    // --- Free generated keys ---
    for (int i = 0; i < NUM_TEST_KEYS; ++i) {
        free(test_keys[i]);
    }
    free(test_keys);
    printf("-------------------------------------------------------------------\n");
}

void test_8byte_key() {
    srand(time(NULL)); // Initialize random seed for reproducibility

    // Define hash table size M (a large prime number is usually good)
    const int M = 99991; // Common choice for hash table sizes

    // Define the key length for this specific test
    size_t test_key_length = 8; // Testing for 8-byte keys as per your request

    // Number of keys to hash for each length
    const int NUM_TEST_KEYS = 100000; // 10万个键

    printf("Comparing hash function performance for %zu-byte keys (M = %d):\n", test_key_length, M);
    printf("-------------------------------------------------------------------\n");

    // --- Generate random string keys for the current length ---
    char** test_keys = (char**)malloc(NUM_TEST_KEYS * sizeof(char*));
    if (!test_keys) {
        perror("Failed to allocate memory for test_keys array");
        return ;
    }
    for (int i = 0; i < NUM_TEST_KEYS; ++i) {
        test_keys[i] = generate_random_string(test_key_length);
        if (!test_keys[i]) {
            perror("Failed to generate random string key");
            // Clean up already allocated strings before exiting
            for (int j = 0; j < i; ++j) free(test_keys[j]);
            free(test_keys);
            return ;
        }
    }

    // --- Measure time for Program 14.1 hash function ---
    double time_hash_1401 = measure_hash_time(hash_1401, test_keys, NUM_TEST_KEYS, M);
    printf("Program 14.1 Hash (char by char): %f seconds\n", time_hash_1401);

    // --- Measure time for Optimized hash function ---
    double time_hash_optimized_4byte = measure_hash_time(hash_optimized_4byte, test_keys, NUM_TEST_KEYS, M);
    printf("Optimized Hash (4 bytes at a time): %f seconds\n", time_hash_optimized_4byte);

    // --- Calculate and print speedup ---
    if (time_hash_1401 > 0 && time_hash_optimized_4byte > 0) {
        printf("Speedup (14.1 / Optimized): %.2fx\n", time_hash_1401 / time_hash_optimized_4byte);
    } else {
        printf("Speedup (14.1 / Optimized): Cannot calculate (one of the times is zero or invalid)\n");
    }
    printf("\n");

    // --- Free generated keys ---
    for (int i = 0; i < NUM_TEST_KEYS; ++i) {
        free(test_keys[i]);
    }
    free(test_keys);
    printf("-------------------------------------------------------------------\n");
}

void test_16byte_key() {
    srand(time(NULL)); // Initialize random seed for reproducibility

    // Define hash table size M (a large prime number is usually good)
    const int M = 99991; // Common choice for hash table sizes

    // Define the key length for this specific test
    size_t test_key_length = 16;

    // Number of keys to hash for each length
    const int NUM_TEST_KEYS = 100000; // 10万个键

    printf("Comparing hash function performance for %zu-byte keys (M = %d):\n", test_key_length, M);
    printf("-------------------------------------------------------------------\n");

    // --- Generate random string keys for the current length ---
    char** test_keys = (char**)malloc(NUM_TEST_KEYS * sizeof(char*));
    if (!test_keys) {
        perror("Failed to allocate memory for test_keys array");
        return ;
    }
    for (int i = 0; i < NUM_TEST_KEYS; ++i) {
        test_keys[i] = generate_random_string(test_key_length);
        if (!test_keys[i]) {
            perror("Failed to generate random string key");
            // Clean up already allocated strings before exiting
            for (int j = 0; j < i; ++j) free(test_keys[j]);
            free(test_keys);
            return ;
        }
    }

    // --- Measure time for Program 14.1 hash function ---
    double time_hash_1401 = measure_hash_time(hash_1401, test_keys, NUM_TEST_KEYS, M);
    printf("Program 14.1 Hash (char by char): %f seconds\n", time_hash_1401);

    // --- Measure time for Optimized hash function ---
    double time_hash_optimized_4byte = measure_hash_time(hash_optimized_4byte, test_keys, NUM_TEST_KEYS, M);
    printf("Optimized Hash (4 bytes at a time): %f seconds\n", time_hash_optimized_4byte);

    // --- Calculate and print speedup ---
    if (time_hash_1401 > 0 && time_hash_optimized_4byte > 0) {
        printf("Speedup (14.1 / Optimized): %.2fx\n", time_hash_1401 / time_hash_optimized_4byte);
    } else {
        printf("Speedup (14.1 / Optimized): Cannot calculate (one of the times is zero or invalid)\n");
    }
    printf("\n");

    // --- Free generated keys ---
    for (int i = 0; i < NUM_TEST_KEYS; ++i) {
        free(test_keys[i]);
    }
    free(test_keys);
    printf("-------------------------------------------------------------------\n");
}

void test_32byte_key() {
    srand(time(NULL)); // Initialize random seed for reproducibility

    // Define hash table size M (a large prime number is usually good)
    const int M = 99991; // Common choice for hash table sizes

    // Define the key length for this specific test
    size_t test_key_length = 32; // Testing for 4-byte keys as per your request

    // Number of keys to hash for each length
    const int NUM_TEST_KEYS = 100000; // 10万个键

    printf("Comparing hash function performance for %zu-byte keys (M = %d):\n", test_key_length, M);
    printf("-------------------------------------------------------------------\n");

    // --- Generate random string keys for the current length ---
    char** test_keys = (char**)malloc(NUM_TEST_KEYS * sizeof(char*));
    if (!test_keys) {
        perror("Failed to allocate memory for test_keys array");
        return ;
    }
    for (int i = 0; i < NUM_TEST_KEYS; ++i) {
        test_keys[i] = generate_random_string(test_key_length);
        if (!test_keys[i]) {
            perror("Failed to generate random string key");
            // Clean up already allocated strings before exiting
            for (int j = 0; j < i; ++j) free(test_keys[j]);
            free(test_keys);
            return ;
        }
    }

    // --- Measure time for Program 14.1 hash function ---
    double time_hash_1401 = measure_hash_time(hash_1401, test_keys, NUM_TEST_KEYS, M);
    printf("Program 14.1 Hash (char by char): %f seconds\n", time_hash_1401);

    // --- Measure time for Optimized hash function ---
    double time_hash_optimized_4byte = measure_hash_time(hash_optimized_4byte, test_keys, NUM_TEST_KEYS, M);
    printf("Optimized Hash (4 bytes at a time): %f seconds\n", time_hash_optimized_4byte);

    // --- Calculate and print speedup ---
    if (time_hash_1401 > 0 && time_hash_optimized_4byte > 0) {
        printf("Speedup (14.1 / Optimized): %.2fx\n", time_hash_1401 / time_hash_optimized_4byte);
    } else {
        printf("Speedup (14.1 / Optimized): Cannot calculate (one of the times is zero or invalid)\n");
    }
    printf("\n");

    // --- Free generated keys ---
    for (int i = 0; i < NUM_TEST_KEYS; ++i) {
        free(test_keys[i]);
    }
    free(test_keys);
    printf("-------------------------------------------------------------------\n");
}